8735. Сортировщик поезда

На старой железнодорожной станции вы всё ещё можете встретить одного из последних оставшихся сортировщиков поездов. Сортировщик поезда – это работник железной дороги, чья единственная задача заключается в перестановке вагонов поездов. После того как вагоны расставлены в правильном порядке, машинисту остаётся лишь поочерёдно отправлять их на станции, для которых предназначен груз.

Название “сортировщик поезда” происходит от первого человека, выполнившего эту задачу на станции, расположенной рядом с железнодорожным мостом. Вместо вертикального открытия мост вращался вокруг колонны в центре реки. Повернув мост на 90 градусов, лодки могли проходить влево или вправо.

Первый сортировщик поезда обнаружил, что мост может выдерживать максимум два вагона одновременно. Повернув мост на 180 градусов, вагоны менялись местами, что позволило ему переставлять их (как побочный эффект, вагоны затем оказывались в противоположном направлении, но так как поезда могут двигаться в любом направлении, это не представляло проблемы).

Теперь, когда почти все железнодорожные сортировщики вымерли, железнодорожная компания стремится автоматизировать их работу. Часть программы, которая должна быть разработана, – это процедура, определяющая для данного поезда минимальное количество перестановок двух соседних вагонов, необходимых для приведения поезда в правильный порядок. Ваша задача – создать такую программу.

Вход. Первая строка содержит количество тестов n. Каждый тест состоит из двух строк. Первая строка теста содержит целое число l (0 ≤ l ≤ 10000) – длину поезда. Вторая строка теста содержит перестановку чисел от 1 до l, определяющую текущий порядок вагонов. Вагоны должны быть упорядочены так, чтобы вагон 1 шел первым, затем вагон 2 и так далее, а вагон l был последним.

Выход. Для каждого теста выведите предложение: “Optimal train swapping takes s swaps.”, где s – целое число, обозначающее минимальное количество необходимых перестановок.

Пример входа	Пример выхода
3 3 1 3 2 4 4 3 2 1 2 2 1	Optimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps.

РЕШЕНИЕ

инверсии

Анализ алгоритма

Пусть массив m содержит входную перестановку – текущий порядок вагонов. Искомое минимальное количество перестановок равно числу инверсий в этой перестановке.

Инверсией называется такая пара элементов (m_i, m_j), что i < j, но при этом m_i > m_j. Иными словами, пара элементов образует инверсию, если они расположены в неправильном порядке.

Например в массиве m = {3, 1, 2} инверсии образуют пары (3, 1) и (3, 2). Пара (1, 2) инверсии не образует, так как числа 1 и 2 расположены относительно друг друга в правильном порядке.

Количество инверсий в массиве длины n можно посчитать при помощи двойного цикла: переберем все возможные пары (i, j), для которых 1 ≤ i < j ≤ n, и если m_i > m_j, увеличим счётчик инверсий на единицу.

Пример

Рассмотрим пример подсчета инверсий в перестановке. Под каждым числом запишем количество инверсий, которые оно образует с элементами, стоящими правее него. Пусть inv[i] обозначает количество таких индексов j, для которых i < j и m[i] > m[j].

Общее количество инверсий равно 16.

Упражнение

Промоделируйте решение для следующего примера.

Реализация алгоритма

Объявим массив m.

int m[100010];

Последовательно обрабатываем tests тестов.

scanf("%d", &tests);

while (tests--)

{

Входной порядок вагонов читаем в массив m.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Минимальное количество перестановок, необходимых для упорядочивания поезда, подсчитываем в переменной res.

res = 0;

for (i = 0; i < n - 1; i++)

for (j = i + 1; j < n; j++)

if (m[i] > m[j]) res++;

Выводим ответ.

printf("Optimal train swapping takes %lld swaps.\n", res);

}